package astudy.util;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Set;

public class AdvMath {

	public static BigInteger gcd(BigInteger m, BigInteger n) {

		m = m.abs();
		n = n.abs();
		if (m.equals(BigInteger.ZERO)) {
			return n;
		} else if (n.equals(BigInteger.ZERO)) {
			return m;
		} else if (m.compareTo(n) > 0) {
			return gcd(n, m.remainder(n));
		} else if (m.compareTo(n) < 0) {
			return gcd(m, n.remainder(m));
		} else {
			return m;
		}
	}
	
	public static BigInteger gcd(List<BigInteger> l) {
		
		if (l != null) {
			BigInteger gcd = l.get(0);
			for (int i = 1; i < l.size(); i ++) {
				gcd = gcd(gcd, l.get(i));
			}
			return gcd;
		} else {
			return BigInteger.ZERO;
		}
	}

	public static BigInteger lcd(BigInteger m, BigInteger n) {
		
		m = m.abs();
		n = n.abs();
		if (m.equals(BigInteger.ZERO) || n.equals(BigInteger.ZERO)) {
			return BigInteger.ZERO;
		} else {
			BigInteger gcd = gcd(m,n);
			return m.divide(gcd).multiply(n);
		}
	}
	
	public static BigInteger lcd(List<BigInteger> l) {
		
		if (l != null) {
			BigInteger lcd = l.get(0);
			for (int i = 1; i < l.size(); i ++) {
				lcd = lcd(lcd, l.get(i));
			}
			return lcd;
		} else {
			return BigInteger.ZERO;
		}
	}
	
	/**
	 * C(m,n)
	 * @param m
	 * @param n
	 */
	public static BigInteger combine(BigInteger m, BigInteger n) {
		
		if (m.compareTo(BigInteger.ZERO) < 0 || n.compareTo(BigInteger.ZERO) < 0) {
			return BigInteger.ZERO;
		} else if (n.compareTo(m) > 0) {
			return BigInteger.ZERO;
		} else if (n.compareTo(m.divide(BigInteger.valueOf(2))) > 0) {
			return combine(m, m.subtract(n));
		} else {
			BigInteger r = BigInteger.ONE;
			BigInteger i = BigInteger.ZERO;
			while (i.compareTo(n) < 0) { 
				r = r.multiply(m.subtract(i));
				i = i.add(BigInteger.ONE);
				r = r.divide(i);
			}
			return r;
		}
	}

	/**
	 * (m_1+...+m_n)!/(m_1!m_2!...m_n!)
	 * @param ms
	 * @return
	 */
	public static BigInteger combine(BigInteger... ms) {

		if (ms == null || ms.length == 0) {
			return BigInteger.ZERO;
		} else {
			BigInteger sum = BigInteger.ZERO;
			for (BigInteger m : ms) {
				if (m.compareTo(BigInteger.ZERO) < 0) {
					return BigInteger.ZERO;
				} else {
					sum = sum.add(m);
				}
			}
			BigInteger r = BigInteger.ONE;
			BigInteger i, j = sum;
			for (BigInteger m : ms) {
				i = BigInteger.ZERO;
				while (i.compareTo(m) < 0) {
					r = r.multiply(j);
					j = j.subtract(BigInteger.ONE);
					i = i.add(BigInteger.ONE);
					r = r.divide(i);
				}
			}
			return r;
		}
	}

	public static long gcd(long x, long y) {

		if (x == 0) { return y; }
		if (y == 0) { return x; }
		if (x >= y) {
			return gcd(x%y, y);
		} else {
			return gcd(y%x, x);
		}
	}
	
	public static long lcd(long x, long y) {
		return x*y/gcd(x,y);
	}
	
	public static long phi(long n) {
		
		Long[] ds = primeDivisor(n);
		for (Long d: ds) {
			n = n/d * (d-1);
		}
		return n;
	}
	
	/**
	 * 采用类似筛法的方式，计算所有n(<m)对应的phi(n)
	 * @param m
	 * @return
	 */
	public static int[] phis(Integer m) {
		
		int sqrt_m = (int)Math.sqrt(m)+1;
		Integer[] primes = AdvMath.primes(sqrt_m);
		
		/**
		 * 注意:变量tmp, res不要申明为Integer[]。
		 * Integer需要的资源太多，导致程序总是在物理内存和虚拟内存的之间过多的转换，导致效率低下。
		 */
		int[] tmp = new int[m+1];
		int[] res = new int[m+1];
		for (int i = 0; i < tmp.length; i ++) {
			tmp[i] = i;
			res[i] = 1;
		}
		
		tmp[0] = -1;
		res[0] = -1;
		tmp[1] = 1;
		res[1] = 1;
		
		for (int i = 0; i < primes.length; i ++) {
			int p = primes[i];
			for (int j = p; j <= m; j += p) {
				while (tmp[j]%p == 0) {
					tmp[j] /= p;
					res[j] *= p;
				}
				res[j] /= p;
				res[j] *= p-1;
			}
		}
		for (int i = 1; i < tmp.length; i ++) {
			if (tmp[i] != 1) {
				res[i] *= tmp[i]-1; 
			}
		}

		return res;
	}

	
	public static Long[] primeDivisor(long n) {

		long m = n;
		List<Long> ds = new ArrayList<Long>();
		while (m > 1) {
			Long p = minPrimeDivisor(m);
			ds.add(p);
			while (m%p == 0) {
				m /= p;
			}
		}
		return ds.toArray(new Long[ds.size()]);
	}
	
	public static Long minPrimeDivisor(long n) {
		
		for (long i = 2; i <= Math.sqrt(n); i ++) {
			if (isPrime(i) && n%i == 0) {
				return i;
			}
		}
		return n;
	}
	
	/**
	 * prime numbers < m 
	 * @param m
	 * @return
	 */
	public static Integer[] primes(int m) {
		
		List<Integer> ps = new ArrayList<Integer>();
		int[] tmp = new int[m+1];
		for (int i = 0; i < tmp.length; i ++) {
			tmp[i] = i;
		}
		tmp[0] = -1;
		tmp[1] = -1;
		int p = 2;
		boolean f = true;
		while (true) {
			if (f) {
				ps.add(p);
				for (int i = p*2; i < tmp.length; i += p) {
					tmp[i] = -1;
				}
			} else {
				break;
			}
			f = false;
			for (int i = p+1; i < tmp.length; i ++) {
				if (tmp[i] != -1) {
					p = i;
					f = true;
					break;
				}
			}
		}
		
		return ps.toArray(new Integer[ps.size()]);
	}
	
	public static boolean isPrime(long x) {

		if (x == 1) {
			return false;
		} else {
			long y = (long)Math.sqrt(x);
			for (long i = 2; i <= y; i ++) {
				if (x%i == 0) {
					return false;
				}
			}
			return true;
		}
	}
	
	/**
	 * the nth prime number
	 * @param n
	 * @return
	 */
	public static long prime(int n) {
		
		int p = 1;
		while (true) {
			while (true) {
				p ++;
				if (isPrime(p)) {
					n --;
					break;
				}
			}
			
			if (n == 0) {
				return p;
			}
		}
	}
	
	public static class Factors extends HashMap<Long, Integer> {

		private static final long serialVersionUID = 2608611002938490535L;
	
		public Factors() {
		}
		
		public Factors(Factors factors) {
			super(factors);
		}
		
		public Factors(long n) {
			long m = n;
			while (m > 1) {
				int t = (int)Math.sqrt(m)+2;
				int c = 0;
				int i;
				for (i = 2; i < t; i ++) {
					while (m%i == 0) {
						c ++;
						m /= i;
					}
					if (c > 0) {
						this.put(Long.valueOf(i), c);
						c = 0;
					} else if (i == t-1 && m > 1) {
						this.put(Long.valueOf(m), 1);
						m = 1;
					}
				}
			}
		}
		
		public String toString() {
 
			return String.valueOf(this.longValue());
		}
		
		public long longValue() {
			
			long tmp = 1L;
			for (Long p: this.keySet()) {
				tmp *= Math.pow(p, this.get(p));
			}
			return tmp;
		}
		
		public Factors divide(Factors factors) {
			
			Factors f = new Factors();
			if (factors.longValue() == 1L) {
				for (Long p: this.keySet()) {
					f.put(p, this.get(p));
				}
			} else {
				for (Long p: factors.keySet()) {
					if (this.get(p) == null) {
						f.put(p, -factors.get(p));
					} else {
						f.put(p, this.get(p)-factors.get(p));
					}
				}
			}
			return f;
		}
		
		public Factors multiply(Factors factors) {
			
			Factors f = new Factors();
			for (Long p: factors.keySet()) {
				if (this.get(p) == null) {
					f.put(p, factors.get(p));
				} else {
					f.put(p, this.get(p)+factors.get(p));
				}
			}
			return f;
		}
		
		public Factors gcd(Factors factors) {
			
			Factors f = new Factors();
			for (Long p: factors.keySet()) {
				if (this.get(p) == null) {
				} else {
					f.put(p, Math.min(this.get(p), factors.get(p)));
				}
			}
			return f;
		}
		
		public long getDivisorCount() {
		
			long c = 1;
			for (Long p: this.keySet()) {
				c *= (this.get(p)+1);
			}
			return c;
		}
		
		public List<Factors> getAllFactors() {

			Set<Long> keys = this.keySet(); 
			Long[] ps = keys.toArray(new Long[keys.size()]);
			Integer[] ns = new Integer[ps.length];
			for (int i = 0; i < ns.length; i ++) ns[i] = this.get(ps[i]);
			
			Integer[] as = new Integer[ns.length];
			for (int i = 0; i < as.length; i ++) as[i] = 0;
			
			List<Factors> r = new ArrayList<Factors>();
			while (as != null) {
				Factors tmp = new Factors();
				for (int i = 0; i < as.length; i ++) {
					if (as[i] > 0) {
						tmp.put(ps[i], as[i]);
					}
				}
				r.add(tmp);
				as = findNext(as, ns);
			}
			return r;
		}
		
		/**
		 * as[i] <= ns[i]  
		 * @param as
		 * @param ns
		 * @return
		 */
		private Integer[] findNext(Integer[] as, Integer[] ns) {
			
			int j = ns.length-1;
			while (j > -1 && as[j] == ns[j]) j --;
			if (j == -1) {
				return null;
			} else {
				as[j] += 1;
				for (int i = j+1; i < ns.length; i ++) as[i] = 0;
				return as;
			}
		}
		
		public Factors merge(Factors f) {

			Factors tmp = new Factors();
			for (Long p: this.keySet()) {
				tmp.put(p, this.get(p));
			}
			for (Long p: f.keySet()) {
				if (tmp.get(p) == null) {
					tmp.put(p, f.get(p));
				} else {
					tmp.put(p, tmp.get(p)+f.get(p));
				}
			}
			return tmp;
		}

		/**
		 * 返回1~m所有自然数的Factors
		 * @param m
		 * @return
		 */
		public static Factors[] factor(int m) {

			int sqrt_m = (int)Math.sqrt(m)+1;
			Integer[] primes = AdvMath.primes(sqrt_m);
			
			int[] tmp = new int[m+1];
			Factors[] res = new Factors[m+1];
			for (int i = 0; i < tmp.length; i ++) {
				tmp[i] = i;
				res[i] = new Factors();
			}
			
			tmp[0] = -1;
			res[0] = null;
			tmp[1] = 1;
			res[1] = null;
			
			for (int i = 0; i < primes.length; i ++) {
				int p = primes[i];
				for (int j = p; j <= m; j += p) {
					int count = 0;
					while (tmp[j]%p == 0) {
						tmp[j] /= p;
						count ++;
					}
					res[j].put((long)p, count);
				}
			}
			for (int i = 1; i < tmp.length; i ++) {
				if (tmp[i] != 1) {
					res[i].put((long)tmp[i], 1); 
				}
			}

			return res;
		}
	}
	
	public static Factors merge(Factors f1, Factors f2) {
		
		return f1.merge(f2);
	}
	
	public static Factors factor(long n) {
		
		return new Factors(n);
	}
	
	public static long C(int m, int n) {
		
		if (m < n) {
			return 0L;
		} else {
			if (n > m/2) {
				n = m-n;
			}
			long r = 1L;
			for (int i = 0; i < n; i ++) {
				r *= (m-i);
				r /= (i+1);
			}
			return r;
		}
	}
	
	/**
	 * 给出方程ax+by=gcd(a,b)的一组解
	 * 返回{x,y,gcd(a,b)}
	 * @param a
	 * @param b
	 * @return
	 */
	public static long[] equation(long a, long b) {
		
		if (a == 0) {
			return new long[] {0, 1, b};
		}
		if (b == 0) {
			return new long[] {1, 0, a};
		}
		if (a < 0) {
			long[] ans = equation(-a, b);
			return new long[] {-ans[0], ans[1], ans[2]};
		}
		if (b < 0) {
			long[] ans = equation(a, -b);
			return new long[] {ans[0], -ans[1], ans[2]};
		}
		if (a < b) {
			long[] ans = equation(b, a);
			return new long[] {ans[1], ans[0], ans[2]};
		}
		if (a > b) {
			long[] ans = equation(b, a%b);
			return new long[] {ans[1], ans[0]-ans[1]*(a/b), ans[2]}; 
		}
		return null;
	}
}
